package com.sheng.leetcode.year2022.month06.day01;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/06/01
 *
 * 473. 火柴拼正方形
 *
 * 你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。
 * 你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，
 * 但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。
 * 如果你能使这个正方形，则返回 true ，否则返回 false 。
 *
 * 示例 1:
 *
 * 输入: matchsticks = [1,1,2,2,2]
 * 输出: true
 * 解释: 能拼成一个边长为2的正方形，每边两根火柴。
 * 示例 2:
 *
 * 输入: matchsticks = [3,3,3,3,4]
 * 输出: false
 * 解释: 不能用所有火柴拼成一个正方形。
 *
 * 提示:
 *
 * 1 <= matchsticks.length <= 15
 * 1 <= matchsticks[i] <= 108
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/matchsticks-to-square
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0473 {

    @Test
    public void test01(){
//        int[] matchsticks = {1,1,2,2,2};
        int[] matchsticks = {3,3,3,3,4};
        System.out.println(new Solution().makesquare(matchsticks));
    }

}
class Solution {
    public boolean makesquare(int[] matchsticks) {
        //火柴数量小于4个，直接false
        if (matchsticks.length < 4) {
            return false;
        }
        //火柴总长度
        int sum = 0;
        //最长的火柴的长度
        int max = 0;
        for (int i = 0; i < matchsticks.length; i++) {
            max = Math.max(max, matchsticks[i]);
            sum += matchsticks[i];
        }
        //围城的正方形的边长
        int avg = sum / 4;
        //如果总长度除以4除不尽或者最长的火柴长度大于边长，直接false
        if (sum % 4 != 0 || max > avg) {
            return false;
        }
        //对数组进行排序
        Arrays.sort(matchsticks);
        return dfs(matchsticks, matchsticks.length - 1, new int[4], avg);
    }

    /**
     * 是否可以围成正方形
     *
     * @param nums 火柴数组
     * @param index 数组的索引，从后往前，每次减一
     * @param sums 长度为4的int数组，代表正方形的4条边长
     * @param avg 要围成的正方形的边长
     * @return true/false
     */
    public boolean dfs(int[] nums, int index, int[] sums, int avg) {
        //如果index == -1，代表每条边都已经使用到了，已经迭代完成
        if (index == -1) {
            return true;
        }
        //循环4次
        for (int i = 0; i < 4; i++) {
            //判断sums[i]和nums[index]加起来是否超过边长，不超过就加给sums[i]，然后进行迭代
            if (sums[i] + nums[index] <= avg) {
                sums[i] += nums[index];
                if (dfs(nums, index - 1, sums, avg)) {
                    return true;
                }
                //走到这里说明前面走不通，返回继续迭代
                sums[i] -= nums[index];
            }
        }
        return false;
    }
}

//https://www.jianshu.com/p/20323c84c5c6
//https://blog.csdn.net/bo123_/article/details/105848237
